package day01.归并算法;

import util.ListNode;

import java.util.PriorityQueue;

/**
 * @author wangxi created on 2024/6/24 13:19
 * @version v1.0
 *
 * https://leetcode.cn/problems/merge-k-sorted-lists/
 *
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 * 时间复杂度：最坏 NlogK
 *
 * 两两顺序合并：最坏应该是kN
 */
public class MergeKLists {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length <= 0) {
            return null;
        }
        ListNode head = null;
        ListNode cur = null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>((node1, node2) -> {
            return node1.val - node2.val;
        });
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                queue.add(lists[i]);
            }
        }
        while (!queue.isEmpty()) {
            ListNode min = queue.poll();
            if (head == null || cur == null) {
                head = min;
                cur = min;
            } else {
                cur.next = min;
                cur = min;
            }
            if (min.next != null) {
                queue.add(min.next);
            }
        }
        return head;
    }
}
